package com.atwulidun.idivideandconquer02;

import java.util.Arrays;

public class BigNumMultiplicatiion {
    public static void main(String[] args) {
        String num1 = "11111111111111111111111111111111111111";
        String num2 = "1111111111111111111111";
        System.out.println(multiply(num1, num2));
    }

    // 传入两个大整数字符串，返回两者乘积的字符串
    public static String multiply(String num1, String num2) {
        // 若num1或num2有一个为空字符串，则返回一个空字符串
        if (num1.length() == 0 || num2.length() == 0) {
            return "";
        }
        // 创建一个存放乘积的临时数组，该数组的长度为两个字符串的长度之和：
        // 当两数的最高位相乘不进位时，临时数组的第一位数字为0，乘积有效长度为临时数组的长度-1；
        // 当两数的最高位相乘进位是，乘积有效长度为临时数组的长度
        int[] product = new int[num1.length() + num2.length()];
        // num1在下，num2在上，则num1对应外循环，num2对应内循环
        // 注意：相乘是从数组的最右边开始逐位相乘
        for (int i = num1.length() - 1; i >= 0; i--) {
            for (int j = num2.length() - 1; j >= 0; j--) {
                // 获取逐位相乘的乘积
                int pro = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');// - '0'是为了把char转换为int
                // pro对应的低位为i+j+1
                // 更新低位的值：为当前乘积的值加上之前该低位的值(0~9)
                pro += product[i + j + 1];
                // 更新后低位的值可能超过9，因此要将其对10取余
                product[i + j + 1] = pro % 10;
                // 高位可能有进位
                product[i + j] = pro / 10;
            }
        }
        // 把临时数组前面多于的0给去掉
        int i = 0;
        while (i < product.length && product[i] == 0) {
            i++;
        }
        // 将临时数组中的有效元素进行拼接
        StringBuilder stringBuilder = new StringBuilder();
        while (i < product.length) {
            stringBuilder.append(product[i]);
            i++;
        }
        return stringBuilder.toString();
        // 这里要注意：Arrays.toString(product)方法的效果是：[0, 1, 2, 1]，而不是0121，故要用StringBuilder来进行字符串的拼接！！！！！！！！
    }

    // 以下是用分治算法来计算两个大整数的乘积

}
